package org.example;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/*
贪心算法
贪心的本质是选择每一阶段的局部最优，从而达到全局最优
贪心一般解题步骤：
1. 将问题分解为若干子问题
2. 找出适合的贪心策略
3. 求解每一个子问题的最优解
4. 将局部最优解堆叠成全局最优
*/
public class Greedy {
    // 455. 分发饼干
    // 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
    // 对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。
    // 如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。

    // 思路：这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩
    // 可以尝试使用贪心策略，先将饼干数组和小孩数组排序。
    // 然后从后往前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。
    static class FindContentChildren {
        // 思路一：优先考虑胃口，先喂饱大胃口
        public int findContentChildren(int[] g, int[] s) {
            Arrays.sort(g);
            Arrays.sort(s);
            int count = 0;
            int start = s.length - 1;
            // 遍历胃口
            for (int index = g.length - 1; index >= 0; index--) {
                if (start >= 0 && g[index] <= s[start]) {
                    start--;
                    count++;
                }
            }
            return count;
        }

        // 思路二：优先考虑饼干，小饼干先喂饱小胃口
        public int findContentChildren1(int[] g, int[] s) {
            Arrays.sort(g);
            Arrays.sort(s);
            int count = 0;
            int start = 0;
            for (int i = 0; i < s.length && start < g.length; i++) {
                if (s[i] >= g[start]) {
                    start++;
                    count++;
                }
            }
            return count;
        }
    }

    // 452. 用最少数量的箭引爆气球
    // 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，
    // 其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
    // 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，
    // 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
    // 给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

    // 示例 1：
    //
    // 输入：points = [[10,16],[2,8],[1,6],[7,12]]
    // 输出：2
    // 解释：气球可以用2支箭来爆破:
    // -在x = 6处射出箭，击破气球[2,8]和[1,6]。
    // -在x = 11处发射箭，击破气球[10,16]和[7,12]。

    // 思路：局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。
    // 为了让气球尽可能的重叠，需要对数组进行排序

    // 如果气球重叠了，重叠气球中有边界的最小值之前的区间一定需要一个弓箭

    // 注意：题目中说的是，满足xstart <= x <= xend，则该气球会被引爆。那么说明两个气球挨在一起不重叠也可以一起射爆，所以代码中
    // if(points[i][0] > points[i-1][1])不能是>=
    static class FindMinArrowShots {
        /**
         * 时间复杂度 : O(NlogN)  排序需要 O(NlogN) 的复杂度
         * 空间复杂度 : O(logN) java所使用的内置函数用的是快速排序需要 logN 的空间
         */
        public int findMinArrowShots(int[][] points) {
            // 根据气球直径的开始坐标从小到大排序
            // 使用Integer内置比较方法，不会溢出
            Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));

            int count = 1; // points不为空至少需要一支箭
            for (int i = 1; i < points.length; i++) {
                if (points[i][0] > points[i - 1][1]) { // 气球i和气球i1不挨着，注意这里不是>=
                    count++; // 需要一支箭
                } else { // 气球i和气球i-1挨着
                    points[i][1] = Math.min(points[i][1], points[i - 1][1]); // 更新重叠气球最小右边界
                }
            }
            return count;
        }
    }

    // 435.无重叠区间
    // 给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
    // 注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。
    static class EraseOverlapIntervals {
        public int eraseOverlapIntervals(int[][] intervals) {
            // 按照左边界排序
            Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
            int count = 1; // 表示没有重叠的部分
            for (int i = 1; i < intervals.length; i++) {
                if (intervals[i - 1][1] > intervals[i][0]) {
                    intervals[i][1] = Math.min(intervals[i][1], intervals[i - 1][1]);
                    continue;
                } else {
                    count++; // 表示没有重叠的部分
                }
            }
            return intervals.length - count;
        }

        public int eraseOverlapIntervals1(int[][] intervals) {
            Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
            int remove = 0; // 表示要移出区间个数
            int pre = intervals[0][1];
            for (int i = 1; i < intervals.length; i++) {
                if (pre > intervals[i][0]) {
                    remove++;
                    pre = Math.min(pre, intervals[i][1]);
                } else {
                    pre = intervals[i][1];
                }
            }
            return remove;
        }
    }

    // 763. 划分字母区间
    // 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc"
    // 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。
    // 注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
    // 返回一个表示每个字符串片段的长度的列表。
    static class PartitionLabels {
        // 在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点。
        // 可以分为如下两步：
        // 统计每一个字符最后出现的位置
        // 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
        public List<Integer> partitionLabels(String s) {
            List<Integer> list = new LinkedList<>();
            int[] edge = new int[26];
            char[] chars = s.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                edge[chars[i] - 'a'] = i;
            }
            int left = 0;
            int right = 0;
            for (int i = 0; i < chars.length; i++) {
                right = Math.max(right, edge[chars[i] - 'a']);
                if (i == right) {
                    list.add(i - left + 1);
                    left = i;
                }
            }
            return list;
        }

        public static void main(String[] args) {
            String s = "ababcbacadefegdehijhklij";
            new PartitionLabels().partitionLabels(s);
        }
    }

    // 区间合并
    // 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
    // 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
    // 示例 1：
    //
    // 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
    // 输出：[[1,6],[8,10],[15,18]]
    // 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
    static class Merge {
        // 思路：本题的本质其实还是判断重叠区间问题
        // 所以一样的套路，先排序，让所有的相邻区间尽可能的重叠在一起，按左边界，或者右边界排序都可以，处理逻辑稍有不同
        // 按照左边界从小到大排序之后，如果intervals[i][0]<=intervals[i-1][1]即intervals[i]的左边界 <= intervals[i-1]的右边界，则一定有重叠
        // （本题相邻区间也算重贴，所以是<=）
        public int[][] merge1(int[][] intervals) {
            List<int[]> res = new LinkedList<>();
            // 按照左边界排序
            Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));
            // initial start 是最小左边界
            int start = intervals[0][0];
            int rightmostRightBound = intervals[0][1];
            for (int i = 1; i < intervals.length; i++) {
                // 如果左边界大于最大右边界
                if (intervals[i][0] > rightmostRightBound) {
                    // 加入区间，并且更新start
                    res.add(new int[]{start, rightmostRightBound});
                    start = intervals[i][0];
                    rightmostRightBound = intervals[i][1];
                } else {
                    // 更新最大右边界
                    rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]);
                }
            }
            res.add(new int[]{start, rightmostRightBound});
            return res.toArray(new int[res.size()][]);
        }

        public int[][] merge2(int[][] intervals) {
            LinkedList<int[]> res = new LinkedList<>();
            Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));
            res.add(intervals[0]);
            for (int i = 1; i < intervals.length; i++) {
                if (intervals[i][0] <= res.getLast()[1]) {
                    int start = res.getLast()[0];
                    int end = Math.max(intervals[i][1], res.getLast()[1]);
                    res.removeLast();
                    res.add(new int[]{start, end});
                } else {
                    res.add(intervals[i]);
                }
            }
            return res.toArray(new int[res.size()][]);
        }
    }

    // 253. 会议室II
    // 给你输入若干形如 [begin, end] 的区间，代表若干会议的开始时间和结束时间，请你计算至少需要申请多少间会议室。
    static class MeetingRoomBooking {
        // 返回需要申请的会议室数量
        int minMeetingRooms(int[][] meetings) {
            int n = meetings.length;
            int[] begin = new int[n];
            int[] end = new int[n];
            for (int i = 0; i < meetings.length; i++) {
                begin[i] = meetings[i][0];
                end[i] = meetings[i][1];
            }
            // 排序后就是图中的红点
            Arrays.sort(begin);
            // 排序后就是图中的绿点
            Arrays.sort(end);
            // 扫描过程中的计数器
            int count = 0;
            int res = 0;
            int i = 0;
            int j = 0;
            while (i < n && j < n) {
                if (begin[i] < end[j]) {
                    // 如果当前开始时间早于结束时间，说明有新的会议开始，需要增加一个会议室
                    count++;
                    // 移动到下一个开始时间
                    i++;
                } else {
                    // 如果当前开始时间晚于或等于结束时间，说明有会议结束，释放一个会议室
                    count--;
                    // 移动到下一个结束时间
                    j++;
                }
                // 记录扫描过程中的最大值
                res = Math.max(res, count);
            }
            // 返回所需的最大会议室数量
            return res;
        }

        public static void main(String[] args) {
            int[][] meetings = new int[][]{{0, 30}, {5, 10}, {15, 20}};
            new MeetingRoomBooking().minMeetingRooms(meetings);
        }
    }

    // 738.单调递增的数字
    // 给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
    //（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
    //示例 1:
    //输入: N = 10
    //输出: 9
    //示例 2:
    //输入: N = 1234
    //输出: 1234
    //示例 3:
    //输入: N = 332
    //输出: 299
    //说明: N 是在 [0, 10^9] 范围内的一个整数。

    // 题目要求小于等于N的最大单调递增的整数，那么拿一个两位的数字来举例
    // 例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]--，
    // 然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。
    // 此时是从前向后遍历还是从后向前遍历呢？
    // 从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。
    // 这么说有点抽象，举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。
    // 那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299
    // 确定了遍历顺序之后，那么此时局部最优就可以推出全局，找不出反例，试试贪心。


    static class MonotoneIncreasingDigits {
        // java版本1中创建了String数组，多次使用Integer.parseInt了方法，这导致不管是耗时还是空间占用都非常高，用时12ms，
        public int monotoneIncreasingDigits(int N) {
            String[] strings = (N + "").split("");
            int start = strings.length; // 这个值表示从后往前，计算时，将start及后面的值全部赋值为9
            for (int i = strings.length - 1; i > 0; i--) {
                if (Integer.parseInt(strings[i]) < Integer.parseInt(strings[i - 1])) {
                    strings[i - 1] = (Integer.parseInt(strings[i - 1]) - 1) + "";
                    start = i;
                }
            }
            // 从start的位置开始，将后面的值赋值为9
            for (int i = start; i < strings.length; i++) {
                strings[i] = "9";
            }
            return Integer.parseInt(String.join("", strings));
        }

        // 下面提供一个版本在char数组上原地修改，用时1ms的版本
        public int monotoneIncreasingDigits1(int n) {
            String s = String.valueOf(n);
            char[] chars = s.toCharArray();
            int start = s.length();
            for (int i = s.length() - 1; i > 0; i--) {
                if (chars[i] < chars[i - 1]) {
                    chars[i - 1]--;
                    start = i;
                }
            }
            for (int i = start; i < s.length(); i++) {
                chars[i] = '9';
            }
            return Integer.parseInt(String.valueOf(chars));
        }

        public static void main(String[] args) {
            int n = 332;
            new MonotoneIncreasingDigits().monotoneIncreasingDigits1(n);
        }
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // 968.监控二叉树
    // 给定一个二叉树，我们在树的节点上安装摄像头。
    // 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
    // 计算监控树的所有节点所需的最小摄像头数量。
    // 输入：[0,0,null,0,0]
    // 输出：1
    // 解释：如图所示，一台摄像头足以监控所有节点。
    static class MinCameraCover {
        // 这道题目首先要想，如何放置，才能让摄像头最小的呢？
        // 从题目中示例，其实可以得到启发，我们发现题目示例中的摄像头都没有放在叶子节点上！
        // 这是很重要的一个线索，摄像头可以覆盖上中下三层，如果把摄像头放在叶子节点上，就浪费的一层的覆盖。
        // 所以把摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。
        // 那么有同学可能问了，为什么不从头结点开始看起呢，为啥要从叶子节点看呢？
        // 因为头结点放不放摄像头也就省下一个摄像头， 叶子节点放不放摄像头省下了的摄像头数量是指数阶别的。
        // 所以我们要从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！
        // 局部最优推出全局最优，找不出反例，那么就按照贪心来！
        // 此时，大体思路就是从低到上，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头结点。
        // 此时这道题目还有两个难点：
        // 二叉树的遍历
        // 如何隔两个节点放一个摄像头

        // 确定遍历顺序
        // 在二叉树中如何从低向上推导呢？
        // 可以使用+也就是左右中的顺序，这样就可以在回溯的过程中从下到上进行推导了。
        // 后序遍历代码如下：
        // int traversal(TreeNode* cur) {
        //    // 空节点，该节点有覆盖
        //    if (终止条件) return ;
        //    int left = traversal(cur->left);    // 左
        //    int right = traversal(cur->right);  // 右
        //    逻辑处理                            // 中
        //    return ;
        //}
        // 注意在以上代码中我们取了左孩子的返回值，右孩子的返回值，即left 和 right， 以后推导中间节点的状态

        // 如何隔两个节点放一个摄像头
        // 此时需要状态转移的公式，大家不要和动态的状态转移公式混到一起，本题状态转移没有择优的过程，就是单纯的状态转移！
        // 来看看这个状态应该如何转移，先来看看每个节点可能有几种状态：
        // 有如下三种：
        // 该节点无覆盖
        // 本节点有摄像头
        // 本节点有覆盖
        // 我们粉末别有三个数字来表示：
        // - 0:该节点无覆盖
        // - 1:本节点有摄像头
        // - 2:本节点有覆盖
        // 主要有如下四类情况：
        // 情况1：左右节点都有覆盖,左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。
        // 情况2：左右节点至少有一个无覆盖的情况
        // 情况3：左右节点至少有一个有摄像头
        // 情况4：头结点没有覆盖
        // 以上都处理完了，递归结束之后，可能头结点 还有一个无覆盖的情况，如图：
        int res = 0;

        public int minCameraCover(TreeNode root) {
            // 对根节点状态做校验，防止根节点是无覆盖状态
            if (minCame(root) == 0) {
                res++;
            }
            return res;
        }

        /*
        节点的状态值：
        0 表示无覆盖
        1 表示有摄像头
        2 表示有覆盖
        后序遍历，根据左右节点的情况,来判读 自己的状态*/
        public int minCame(TreeNode root) {
            if (root == null) {
                // 空节点默认为：有覆盖状态，避免在叶子节点上放摄像头
                return 2;
            }
            // 左右中
            int left = minCame(root.left);
            int right = minCame(root.right);
            // 如果左右节点都覆盖了，那么本节点的状态就应该是无覆盖，没有摄像头
            if (left == 2 && right == 2) {
                return 0;
            } else if (left == 0 || right == 0) {
                // 左右节点都是无覆盖状态，那么根节点此时应该放一个摄像头
                res++;
                return 1;
            } else {
                // 左右节点的状态为（1,1）（1,2）（2,1）也就是左右节点至少存在一个摄像头
                // 那么本节点就是处于被覆盖状态
                return 2;
            }
        }
    }
}


